#include "headfiles.h"

static map<char *, bool> word_hit_flag;

bool isNeighbor(char *word1, char *word2) {
    size_t len1 = strlen(word1);
    size_t len2 = strlen(word2);

    if (len1 != len2) {
        return false;
    }

    size_t i;
    size_t dist = 0;
    for (i = 0; i < len1; i++) {
        if (word1[i] != word2[i]) {
            ++dist;
        }
    }

    if (dist == 1) {
        return true;
    }
    else {
        return false;
    }
}

bool getWordNeighborList(char *word, 
                         vector<char *> &lex, 
                         vector<char *> &neighbor_list) {
    neighbor_list.clear();
    vector<char *>::iterator it;
    for (it = lex.begin(); it != lex.end(); it++) {
        if (word_hit_flag[*it] == true) {
            continue;
        }

        bool is_neighbor = isNeighbor(word, *it);
        if (is_neighbor) {
            neighbor_list.push_back(*it);
            word_hit_flag[*it] = true;
        }
    }

    return true;
}

// Return value:
//             1. true - a neighbor is found
//             2. false - no neighbor is found
bool getFirstNeighbor(char *word, 
                      vector<char *> &lex, 
                      char * &neighbor) {
    vector<char *>::iterator it;
    for (it = lex.begin(); it != lex.end(); it++) {
        if (word_hit_flag[*it] == true) {
            continue;
        }

        bool is_neighbor = isNeighbor(word, *it);
        if (is_neighbor) {
            word_hit_flag[*it] = true;
            neighbor = *it;
            return true;
        }
    }

    return false;
}


bool createLex(char *file_name, vector<char *> &lex) {
    if (file_name == NULL) {
        cout << "File name is NULL!" << endl;
        return false;
    }

    fstream fs;
    char word_temp[100];
    fs.open(file_name, fstream::in);
    if (!fs.is_open()) {
        cout << "File " << file_name << " is NOT openned!" << endl;
        return false;
    }

    while (!fs.eof()) {
        fs.getline(word_temp, 100);
        size_t word_len = strlen(word_temp);
        if (word_len == 0) {
            continue;
        }

        char *w = new char[word_len + 1];
        memcpy(w, word_temp, word_len + 1);
        lex.push_back(w);
        word_hit_flag.insert(pair<char*, bool>(w, false));
    }
    fs.close();
    
    return true;
}

bool transformWordDeepFirstSearch(char *word1, 
                                  char *word2, 
                                  vector<char *> &lex, 
                                  vector<char *> &word_list) {
    size_t word_len1 = strlen(word1);
    size_t word_len2 = strlen(word2);

    if (word_len1 != word_len2) {
        return false;
    }

    vector<char *>::iterator it;
    stack<char *> word_stack;
    char *neighbor;
    bool ret;

    word_stack.push(word1);
    while (!word_stack.empty()) {
        char *top_word = word_stack.top();
        ret = getFirstNeighbor(top_word, lex, neighbor);
        if (!ret) {
            word_stack.pop();
        }
        else {
            if (strcmp(neighbor, word2) == 0) {
                word_list.push_back(neighbor);
                while (!word_stack.empty()) {
                    word_list.push_back(word_stack.top());
                    word_stack.pop();
                }
                return true;
            }
            else {
                word_stack.push(neighbor);
            }
        }
    }
    
    cout << word1 << " can be transformed to " << word2 << endl;

    return false;
}

bool transformWordBreadthFirstSearch(char *word1, 
                                    char *word2, 
                                    vector<char *> &lex, 
                                    vector<char *> &word_list) {
    size_t word_len1 = strlen(word1);
    size_t word_len2 = strlen(word2);

    if (word_len1 != word_len2) {
        return false;
    }

    vector<char *> neighbor;
    vector<char *>::iterator it;
    queue<char *> word_queue;
    bool ret;

    word_hit_flag[word1] = true;
    word_queue.push(word1);
    while (!word_queue.empty()) {
        char *word = word_queue.front();
        cout << word << endl;
        word_queue.pop();
        ret = getWordNeighborList(word, lex, neighbor);
        for (it = neighbor.begin(); it != neighbor.end(); it++) {
            if (strcmp(*it, word2) == 0) {
                return true;
            }
            word_queue.push(*it);
        }
    }

    return false;
}


bool transformWord(char *word1, char *word2, vector<char *> &lex, vector<char *> &word_list) {
    size_t word_len1 = strlen(word1);
    size_t word_len2 = strlen(word2);

    if (word_len1 != word_len2) {
        return false;
    }

    word_hit_flag[word1] = true;
    vector<char *> neighbor;
    vector<char *>::iterator it;
    bool ret;
    ret = getWordNeighborList(word1, lex, neighbor);
    if (ret == false) {
        cout << "Get neighbor list for word " << word1 << "error!" << endl;
        return false;
    }
    
    for (it = neighbor.begin(); it != neighbor.end(); it++) {
        if (strcmp(word2, *it) == 0) {
            //cout << "List is created as:" << endl;
            //cout << *it << "\t";
            word_list.push_back(*it);
            return true;
        }
    }

    for (it = neighbor.begin(); it != neighbor.end(); it++) {
        ret = transformWord(*it, word2, lex, word_list);
        if (ret) {
            //cout << *it << "\t";
            word_list.push_back(*it);
            return true;
        }
    }

    return false;
}

